This invention relates to the field of network analysis systems, and in particular to a method and system for determining a topology of one or more networks based on information contained in Address Forwarding Tables (AFT) associated with switches of the network.
Effective management of a network generally requires knowledge of the topology of the network. A preferred user interface for visualization and analysis tools generally provides a display of the topology of the network, wherein colors and other graphic features are used to illustrate features and performance characteristics related to the network nodes and their interconnecting links.
In many situations, and particularly when dealing with large and active networks, the information available for determining how the network nodes are operationally connected to each other is incomplete and/or outdated. As new devices are added to a network, to replace or augment existing capabilities, the database that is used to model the network is often not correspondingly updated; as new routes are created, deleted, or modified, either intentionally or unintentionally, the differences between the actual network and the modeled network continue to increase.
Automated systems have been developed to query devices on the network for their current configuration, and this information is used to update and/or regenerate the network model, including a model of the network topology and other models. Of particular note, switching devices are generally configured to maintain “address forwarding tables” (AFT) that identify the port to which messages addressed to each address should be forwarded. These forwarding tables are generally created dynamically; when a message from a new address is received on a given port, the switch adds the new address to the address forwarding table of the given node, based on the assumption that the network is acyclic and the communication path from and to that address is bidirectional. Conventional bridges use algorithms, such as the Ethernet spanning tree algorithm to assure that the network is acyclic, even in the presence of a cyclic physical configuration. By querying all switches in the network for their current address forwarding tables, the current interconnectivity of the switches can be determined by creating a tree structure based on a determination of which ports are directly connected to each other.
“Topology Discovery in Heterogeneous IP Networks”, by Breitbart et al., Proceedings of INFOCOM 2000, March 2000, provides a technique for determining network topology when substantially complete address forwarding table information is provided. Breitbart determined that, in an acyclic network, if the union of the AFTs of two ports contains all of the network nodes, and the intersection of the AFTs of these two ports is null, then the two ports must be directly connected to each other.
“Topology Discovery for Large Ethernet Networks”, by Lowekamp et al., SIGCOMM '01, August 2001, provides a technique for determining network topology in the absence of complete connectivity data, including the inference of shared link segments that are not explicitly identified in the connectivity data. Lowekamp introduces the term “through set” (TS), which is the set of addresses that are input on a given port and passed through to other ports on the switch. Because the networks are assumed to be acyclic, as is typical of conventional Ethernet bridged networks, these through sets can be used to identify ports that cannot be connected (directly or indirectly) to each other. For ease of reference, the term ‘simply connected’ is used to indicate that two nodes are connected, either directly to each other, or via one or more intermediate nodes. By a process of elimination, and knowing that messages are passed between a pair of nodes, the ports that must be providing this connectivity can be determined. Lowekamp determined that, in an acyclic network, if the through sets of two ports contain an address in common, then those two ports cannot be simply connected; if a single pair of ports on a pair of communicating switches are found with through sets that do not contain an address in common, they must be simply connected. When one or more direct connections cannot be found to establish the link between ports that are determined to be simply connected, the existence of the link can be inferred, and a ‘virtual link’ can be added to the topology. If multiple nodes are identified as being simply connected to the same port, a virtual shared segment can be inferred, such as the use of a public (and not-modeled) network from this port to these multiple nodes.
Although Lowekamp's simply-connected determination provides a technique that is more robust for determining network topology than Breitbart's directly-connected determination when complete connectivity data is not available, both Lowekamp's and Breitbart's techniques are computationally demanding, particularly in a complex network comprising hundreds or thousands of switches, each with multiple ports. Additionally, neither Lowekamp nor Breitbart addresses the merging of their techniques with other known link inference techniques and other connectivity tools; and neither addresses the use of additional information, such as the presence of particularly configured virtual local area networks (VLANs), such as protocol-filtered VLANs, or the presence of aggregate links that logically group individual physical links. In like manner, although Lowekamp's technique can accommodate gaps in connectivity information, Lowekamp does not address the absence of connectivity information relative to entire segments of the network. Lowekamp assumes that all nodes are somehow connected, and, correspondingly, sufficient connectivity information is available for linking all nodes via a tree search starting from a root switch.
It would be advantageous to provide a network topology determining method and system that does not require an exhaustive comparison of the through-set of each port on each switch with the through-set of each port on every other switch on the network. It would also be advantageous to provide a network topology determining method and system that achieves efficiencies based on ancillary information related to the port characteristics. It would also be advantageous to assure that the determined topology includes all identified nodes, regardless of their interdependent connectivity.
These advantages, and others, can be realized by a method and system that partitions a network into a set of independent partitions, determines the topology of each partition, then merges the topologies to form a topology of the entire network. Preferably, the partitioning is hierarchical, wherein the network is partitioned to form individual VLAN partitions, and each of the VLAN partitions is further partitioned based on the nodes that are simply connected to each port of one or more selected root switches within the VLAN partition. Simple connections to each port are efficiently determined based on an aggregate address forwarding table associated with each node. Ancillary information, such as spanning tree or CDP data, may be used to facilitate efficient partitioning and/or to validate inferences that are made with incomplete information.
Throughout the drawings, the same reference numerals indicate similar or corresponding features or functions. The drawings are included for illustrative purposes and are not intended to limit the scope of the invention.